package com.fr.lintcode;

import java.util.ArrayList;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月9日
*时间：上午10:29:57
*/
public class Q103 {
    /**
     * @param head: The first node of linked list.
     * @return: The node where the cycle begins. 
     *           if there is no cycle, return null
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        int count1 = 0;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast != slow) {
            return null;
        } else {
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                count1++;
                if (fast == slow) {
                    break;
                }
            }
            ListNode tmp = head;
            ArrayList<ListNode> list = new ArrayList<>();
            while (!list.contains(tmp)) {
                list.add(tmp);
                tmp = tmp.next;
                count++;
            }
            for (int i = 0; i < count - count1; i++) {
                head = head.next;
            }
            return head;
        }
    }

    @Test
    public void testA() {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        ListNode node = detectCycle(l1);
        System.out.println(node == null);
    }
}
